(1). Field of Invention
The present invention relates to a multiplier, more particularly, to a multiplier for selectively performing an unsigned magnitude multiplication, or a signed magnitude multiplication with a modified Booth algorithm.
(2). Description of the Prior Art
Multiplication is an essential operation in a digital signal processing (hereinafter referred to as a DSP) operation to process image data.
In designing a multiplier, an operation unit such as an arithmetic logic unit (hereinafter referred to as an ALU) of a central processing unit (hereinafter referred to as a CPU) needs a multiplier enabling selective performance of an unsigned magnitude multiplication or a signed magnitude multiplication.
A method for implementing the unsigned magnitude multiplication or the signed magnitude multiplication in the ALU is to use both an unsigned magnitude multiplier and a signed magnitude multiplier. However, this method requires more circuit area because of the use of two multipliers.
Another method for implementing the unsigned magnitude multiplication or the signed magnitude multiplication in the ALU is to make an additional circuit for compensating the difference between an signed magnitude product and an unsigned magnitude product. This method adds the remaining bits, except the most significant bit of other operand, to a final product, when the most significant bit of a certain operand is "1". However, using this method it is difficult to obtain a square layout which is considered to be a benefit of an array multiplier.
A multiplier for performing an unsigned magnitude multiplication or a two's complement multiplication is described in the U.S. Pat. No. 5,153,850 issued on Aug. 24, 1990, entitled "METHOD AND APPARATUS FOR MODIFYING TWO'S COMPLEMENT MULTIPLIER TO PERFORM UNSIGNED MAGNITUDE MULTIPLICATION". The multiplier described in the United States Patent selectively operates the two's complement multiplication or unsigned magnitude multiplication, corrects the two's complement product by an additional circuit, and then achieves an unsigned magnitude product.
Regarding an algorithm for the multiplication, a modified Booth algorithm is described in DIGITAL CMOS CIRCUIT DESIGN (pp. 211-221) written by Macro Annaratone.
The modified Booth algorithm is a type of a recording algorithm, which divides a first operand into predetermined bit-pairs, achieves a partial product as an intermediate result after performing an operation corresponding to respective bit-pairs to a second operand, adds the generated partial product corresponding to the respective bit-pairs to the other operand, and achieves a final result by multiplying between the two operands. In addition, the modified Booth algorithm considers that "0" has no effect on the multiplication, and improves the operating speed of the multiplication.
FIG. 1 is a block diagram of a conventional two's complement multiplier using a Booth algorithm.
As shown in FIG. 1, a general two's complement multiplier comprises an encoder 1, a sign propagate unit 2, a shift and invert unit 3, first to third partial product generators 4,5, and 6, and a carry look-ahead adder 7. The multiplier shown in FIG. 1 is an eight-bit by eight-bit multiplier, "A" is defined as a multiplicand of eight-bit, and "B" is defined as a multiplier of eight-bit.
The operand "B" is inputted to the encoder 1. The encoder 1 codes a bit-pair of the operand "B" divided in every 3 bits, and forms sets of recoded digits (i.e., -2x, -1x, 0x, +1x, and +2x) corresponding to the bit-pair.
Each recoded digit of the recoded digit sets is propagated to one of the unit 3 and three partial product generators 4,5, and 6, respectively. The unit 3 and three partial product generators 4,5, and 6 perform the corresponding operation in relation to the operand "A".
The resulting operation is outputted to outside through the carry look-ahead adder 7. The purpose of the sign propagate unit 2 is to process the extended sign bit of the multiplicand.
Such a multiplier performs a signed magnitude multiplication expressed as two's complement, but cannot perform an unsigned magnitude multiplication.